package binarytree

import "strconv"

func binaryTreePaths(root *TreeNode) []string {

	res := []string{}
	if root == nil {
		return res
	}

	track := []*TreeNode{root}
	var backtrack func()
	backtrack = func() {
		if len(track) == 0 {
			return
		}
		node := track[len(track)-1]

		if node.Left == nil && node.Right == nil {
			str := ""
			for i := 0; i < len(track)-1; i++ {
				str += strconv.Itoa(track[i].Val) + "->"
			}
			str += strconv.Itoa(node.Val)
			res = append(res, str)
			return
		}

		if node.Left != nil {
			track = append(track, node.Left)
			backtrack()
			track = track[:len(track)-1]
		}
		if node.Right != nil {
			track = append(track, node.Right)
			backtrack()
			track = track[:len(track)-1]
		}
	}

	backtrack()
	return res

}

// 迭代
func binaryTreePaths2(root *TreeNode) []string {
	res := []string{}
	if root == nil {
		return res
	}

	stack := []*TreeNode{root}
	paths := []string{""} // 多用一个栈，来记录这个到这个节点之前的路径

	for len(stack) > 0 {

		node := stack[len(stack)-1]
		path := paths[len(paths)-1]
		paths = paths[:len(paths)-1]
		stack = stack[:len(stack)-1]

		if node.Left == nil && node.Right == nil {
			path += strconv.Itoa(node.Val)
			res = append(res, path)
			continue
		}

		if node.Right != nil {
			stack = append(stack, node.Right)
			path += strconv.Itoa(node.Val) + "->"
			paths = append(paths, path)
		}

		if node.Left != nil {
			stack = append(stack, node.Left)
			path += strconv.Itoa(node.Val) + "->"
			paths = append(paths, path)
		}

	}
	return res
}
